feuilles(f,1).
feuilles(n(G,D), R):-feuilles(G,K),feuilles(D,J),R is K+J.

miroir(f,f).
miroir(n(G,D),n(D1,G1)):-miroir(D,D1),miroir(G,G1).

chemins(f,[[]]).
chemins(n(G,D),L):-chemins(G,U), chemins(D,V), chem(U,V,L).

reduce(_,f,E,E).
reduce(P,n(G,D),E,R):-reduce(P,G,E,V1),reduce(P,D,E,V2),Q=..[P,V1,V2,R],Q.


plus(X,Y,Z):-Z is X+Y.

miroir(X,Y,n(Y,X)).

chem([],[],[]).
chem([X|L],[Y|G],[[g|X],[d|Y]|R]):-chem(L,G,R).
chem([],[Y|G],[[d|Y]|R]):-chem([],G,R).
chem([Y|G],[],[[g|Y]|R]):-chem(G,[],R).

/* les buts:
reduce(plus,arbre,1,R) pour feuilles
reduce(miroir,arbre,f,R) pour miroir
reduce(chem,arbre,[[]],R) pour miroir
*/


dec2bin_inv(0,[0]):-!.
dec2bin_inv(1,[1]):-!.
dec2bin_inv(N,[X|L]):-X is N mod 2, K is N//2, dec2bin_inv(K,L).


somme_xor([],L,L).
somme_xor(L,[],L).
somme_xor([X|L],[X|G],[0|R]):-!,somme_xor(L,G,R).
somme_xor([_|L],[_|G],[1|R]):-somme_xor(L,G,R).

somme_xor_iteree([],[]).
somme_xor_iteree([L],L).
somme_xor_iteree([L1,L2|L],R):-somme_xor(L1,L2,U),somme_xor_iteree(L,T),
somme_xor(U,T,R).

bin_inv2dec([],0).
bin_inv2dec([X|L],R):- bin_inv2dec(L,T), R is X + 2*T.


convert([],[]).
convert([N|L],[X|R]):-dec2bin_inv(N,X),convert(L,R).

somme_nim(L,R):-convert(L,B),somme_xor_iteree(B,C),bin_inv2dec(C,R).